{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Pivot Index"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pivotIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找数组的中心下标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> ，请计算数组的 <strong>中心下标 </strong>。</p>\n",
    "\n",
    "<p>数组<strong> 中心下标</strong><strong> </strong>是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。</p>\n",
    "\n",
    "<p>如果中心下标位于数组最左端，那么左侧数之和视为 <code>0</code> ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。</p>\n",
    "\n",
    "<p>如果数组有多个中心下标，应该返回 <strong>最靠近左边</strong> 的那一个。如果数组不存在中心下标，返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1, 7, 3, 6, 5, 6]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "中心下标是 3 。\n",
    "左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，\n",
    "右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1, 2, 3]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>\n",
    "数组中不存在满足此条件的中心下标。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2, 1, -1]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>\n",
    "中心下标是 0 。\n",
    "左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），\n",
    "右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 1991 题相同：<a href=\"https://leetcode-cn.com/problems/find-the-middle-index-in-array/\" target=\"_blank\">https://leetcode-cn.com/problems/find-the-middle-index-in-array/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-pivot-index](https://leetcode.cn/problems/find-pivot-index/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-pivot-index](https://leetcode.cn/problems/find-pivot-index/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,7,3,6,5,6]', '[1,2,3]', '[2,1,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        left_sum = 0\n",
    "        right_sum = sum(nums)\n",
    "        \n",
    "        for i, v in enumerate(nums):\n",
    "            right_sum = right_sum - nums[i]\n",
    "            if left_sum == right_sum:\n",
    "                return i\n",
    "            left_sum = left_sum + nums[i]\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        注意！！！ Note里的话是输入的input，是默认的输入条件，不用检查了\n",
    "        \n",
    "        if len(nums) > 10000 or len(nums) < 1:\n",
    "            return -1\n",
    "        \n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        \n",
    "        if max(nums) > 1000 or min(nums) < -1000:\n",
    "            return -1\n",
    "        \"\"\"\n",
    "        \n",
    "        \"\"\" \n",
    "        我知道你前后插入0是想偷懒....但是reverse是O(n)的复杂度哦，一来一回就是O(2n)了，很慢，具体查阅：https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt\n",
    "        nums.append(0)\n",
    "        nums.append(0)\n",
    "        nums.reverse()\n",
    "        nums.append(0)\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        sum()函数也是O(n)复杂度！！！(你想象看数列一个个加，每加一次就是1，加n次是O(n))\n",
    "        你的for循环就是O(n^2了)\n",
    "        for i in range(1,len(nums)-1):\n",
    "            left=sum(nums[:i])\n",
    "            right=sum(nums[i+1:])\n",
    "            if left==right:\n",
    "                i=i-1\n",
    "                break\n",
    "            else:\n",
    "                i=-1\n",
    "        \"\"\"\n",
    "        \n",
    "        # 以下是我的写法\n",
    "\n",
    "        Sum = sum(nums)\n",
    "        leftSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            \n",
    "            if i > 0:  # 调用[i-1]时，避免报错\n",
    "                leftSum += nums[i-1]\n",
    "            rightSum = Sum - leftSum - nums[i]  # 更新左和右的和只花了O(1)\n",
    "            if leftSum == rightSum:\n",
    "                return i\n",
    "        \n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(nums) > 10000 or len(nums) < 1:\n",
    "            return -1\n",
    "        \n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        \n",
    "        if max(nums) > 1000 or min(nums) < -1000:\n",
    "            return -1\n",
    "        \n",
    "        nums.reverse()\n",
    "        nums.append(0)\n",
    "        nums.reverse()\n",
    "        nums.append(0)\n",
    "  \n",
    "        \n",
    "        for i in range(1,len(nums)-1):\n",
    "            left=sum(nums[:i])\n",
    "            right=sum(nums[i+1:])\n",
    "            if left==right:\n",
    "                i=i-1\n",
    "                break\n",
    "            else:\n",
    "                i=-1\n",
    "                \n",
    "                \n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: 'List[int]') -> 'int':\n",
    "        for i in range(len(nums)):\n",
    "            pre =  nums[:i]\n",
    "            post = nums[i+1:]\n",
    "            if sum(pre) == sum(post):\n",
    "                return i\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        left = 0\n",
    "        right = sum(nums)\n",
    "        for i,v in enumerate(nums):\n",
    "            if left == right - left - v:\n",
    "                return i\n",
    "            left = left + v\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        if not nums:\n",
    "            return -1\n",
    "        sum_nums = sum(nums)\n",
    "        left = 0\n",
    "        for i in range(len(nums)):\n",
    "            if left*2 == sum_nums-nums[i]:\n",
    "                return i\n",
    "            else:\n",
    "                left += nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not nums:\n",
    "            return -1\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        dp = []\n",
    "        sum_temp = 0\n",
    "        for n in nums:\n",
    "            sum_temp += n\n",
    "            dp.append(sum_temp)\n",
    "        for i in range(0, len(nums)):\n",
    "            if dp[i]-nums[i] == dp[-1] - dp[i]:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = sum(nums)\n",
    "        lsum = 0\n",
    "        for i, j in enumerate(nums):\n",
    "            if lsum * 2 + j == res:\n",
    "                return i\n",
    "            lsum += j\n",
    "        return -1            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def addsum(arrays):\n",
    "            addnums = [arrays[0]]\n",
    "            for i in range(1,len(arrays)):\n",
    "                addnums.append(addnums[-1]+arrays[i])\n",
    "            return addnums\n",
    "\n",
    "        def addsum_1(arrays):\n",
    "            addsums = [arrays[-1]]\n",
    "            for i in range(len(arrays)-2,-1,-1):\n",
    "                addsums.insert(0,addsums[0]+arrays[i])\n",
    "            return addsums\n",
    "        if nums == []: \n",
    "            return -1\n",
    "        nums1 = addsum(nums)\n",
    "        nums2 = addsum_1(nums)\n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if nums1[i] == nums2[i]:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if nums == []:\n",
    "            return -1\n",
    "        sum_l =[nums[0]]\n",
    "        sum_n =[nums[-1]]\n",
    "        for i in range(len(nums)-1):\n",
    "            s_l = sum_l[i] + nums[i+1] \n",
    "            sum_l.append(s_l)\n",
    "            s_n = sum_n[i] + nums[-i-2]\n",
    "            sum_n.append(s_n)\n",
    "        sum_n.reverse()\n",
    "        for i in range(len(nums)):\n",
    "            if sum_l[i] ==sum_n[i]:\n",
    "                return i\n",
    "        return -1\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:   \n",
    "    def pivotIndex(self, nums: 'List[int]') -> 'int':\n",
    "        sum_nub = 0\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            sum_nub += i\n",
    "        for i in range(len(nums)):\n",
    "            if not d:\n",
    "                d[i]=0\n",
    "            else:\n",
    "                d[i] = d[i-1] + nums[i-1]\n",
    "            if d[i]*2 + nums[i] == sum_nub:\n",
    "                return i\n",
    "\n",
    "        return -1\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum_nub = 0\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            sum_nub+=i\n",
    "        for i in range(len(nums)):\n",
    "            if not d:\n",
    "                d[i] = 0\n",
    "            else:\n",
    "                d[i] = d[i-1] + nums[i-1]\n",
    "            if d[i] * 2 + nums[i] == sum_nub:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def pivotIndex(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sum_nub = 0\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            sum_nub+=i\n",
    "        for i in range(len(nums)):\n",
    "            if not d:\n",
    "                d[i] = 0\n",
    "            else:\n",
    "                d[i] = d[i-1] + nums[i-1]\n",
    "            if d[i] * 2 + nums[i] == sum_nub:\n",
    "                return i\n",
    "        return -1\n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: 'List[int]') -> 'int':\n",
    "        if len(nums) == 0:\n",
    "            return -1\n",
    "        left = 0\n",
    "        right = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i != 0:\n",
    "                left += nums[i - 1]\n",
    "            right -= nums[i]\n",
    "            if left == right:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: 'List[int]') -> 'int':\n",
    "        right = sum(nums)\n",
    "        left = 0 \n",
    "        for i in range(0,len(nums)):\n",
    "            right = right - nums[i]\n",
    "            if left == right:\n",
    "                return i\n",
    "            left += nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        sumAll = sum(nums)\n",
    "        leftSum = 0\n",
    "        for i in range(len(nums)):\n",
    "            if(i==0):\n",
    "                leftSum=0\n",
    "            else:\n",
    "                leftSum +=nums[i-1]\n",
    "            \n",
    "            if(leftSum*2+nums[i]==sumAll):\n",
    "                return i\n",
    "        return -1  \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        S = sum(nums)\n",
    "        l = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            if l == S-x-l:\n",
    "                return i\n",
    "            l +=x\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        S = sum(nums)\n",
    "        left = 0\n",
    "        for i, data in enumerate(nums):\n",
    "            if left == S - left - nums[i]:\n",
    "                return i\n",
    "            left += nums[i]\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        sum = 0\n",
    "        pivot = -1\n",
    "        for n in nums:\n",
    "            sum += n\n",
    "        cs = 0\n",
    "        for i in range(len(nums)):\n",
    "            if (sum - nums[i]) / 2 == cs:\n",
    "                pivot = i\n",
    "                break\n",
    "            cs += nums[i]\n",
    "        return pivot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        for i,v in enumerate(nums):\n",
    "            if sum(nums[:i]) == sum(nums[i + 1:]):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        total = sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            left = sum(nums[:i])\n",
    "            if left == total - left - nums[i]:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        S = sum(nums)\n",
    "        leftsum = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            if leftsum == (S - leftsum - x):\n",
    "                return i\n",
    "            leftsum += x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            left = sum(nums[:i])\n",
    "            right = sum(nums[i+1:])\n",
    "            if left == right:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        sum_nub = 0\n",
    "        d = {}\n",
    "        for i in nums:\n",
    "            sum_nub+=i\n",
    "        for i in range(len(nums)):\n",
    "            if not d:\n",
    "                d[i] = 0\n",
    "            else:\n",
    "                d[i] = d[i-1] + nums[i-1]\n",
    "            if d[i] * 2 + nums[i] == sum_nub:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        if len(nums) <1:\n",
    "            return -1\n",
    "        resut = -1\n",
    "        m = len(nums)\n",
    "        sum_dict = {}\n",
    "        sum_dict[0] = nums[0]\n",
    "        for index in range(1, m):\n",
    "            sum_dict[index] = nums[index] + sum_dict[index-1]\n",
    "        for i in range(m):\n",
    "            if sum_dict[i]-nums[i] == sum_dict[m-1] - sum_dict[i]:\n",
    "                resut = i\n",
    "                break\n",
    "        return resut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "\n",
    "            if sum(nums[:i]) == sum(nums[i+1:]):\n",
    "                return i \n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for i,ch in enumerate(nums):\n",
    "            if sum(nums[:i])==sum(nums[i+1:n]):\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        leftSum, rightSum = 0, sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            #print(i, leftSum, rightSum)\n",
    "            rightSum -= nums[i]\n",
    "            if leftSum == rightSum:\n",
    "                return i\n",
    "            leftSum += nums[i]\n",
    "        \n",
    "        #if leftSum == rightSum: return len(nums) - 1\n",
    "        #print(leftSum, rightSum)\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        leftSum, rightSum = 0, sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            rightSum -= nums[i]\n",
    "            if leftSum == rightSum:\n",
    "                return i\n",
    "            leftSum += nums[i]\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        left = 0\n",
    "        right = sum(nums) - nums[0]\n",
    "        flag = False\n",
    "        while i < n:\n",
    "            if left == right:\n",
    "                flag = True\n",
    "                break\n",
    "            left += nums[i]\n",
    "            i += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            right -= nums[i]\n",
    "        if not flag:\n",
    "            return -1\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        ls=[]#qs[i]表示坐标nums[i]左边所有元素之和,不含nums[i]\n",
    "        ls.append(0)\n",
    "        for i in range(1,len(nums)):\n",
    "            ls.append(ls[i-1]+nums[i-1])\n",
    "        rs=[]\n",
    "        rs.append(ls[len(nums)-1]-nums[0]+nums[len(nums)-1])\n",
    "        for i in range(1,len(nums)):\n",
    "            rs.append(rs[i-1]-nums[i])\n",
    "        for i in range(len(nums)):\n",
    "            if ls[i]==rs[i]:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        total = sum(nums)\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                left = 0\n",
    "            else:\n",
    "                left = sum(nums[:i])\n",
    "            right = total - left - nums[i]\n",
    "            if right == left:\n",
    "                res.append(i)\n",
    "        if not res:\n",
    "            return -1\n",
    "        return res[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return -1\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        totalSum = sum(nums)\n",
    "        leftSum = 0\n",
    "        rightSum = totalSum - nums[0]\n",
    "        if leftSum == rightSum:\n",
    "            return 0\n",
    "        for i in range(1, len(nums)):\n",
    "            leftSum += nums[i - 1] \n",
    "            rightSum -= nums[i]\n",
    "            if leftSum == rightSum:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        sum_left, sum_right = 0, sum(nums)\n",
    "        for i in range(len(nums)):\n",
    "            sum_right -= nums[i]\n",
    "            # 若左侧元素和等于右侧元素和，返回中心下标 i\n",
    "            if sum_left == sum_right:\n",
    "                return i\n",
    "            sum_left += nums[i]\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotIndex(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return -1\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        totalSum = sum(nums)\n",
    "        leftSum = 0\n",
    "        rightSum = totalSum - nums[0]\n",
    "        if leftSum == rightSum:\n",
    "            return 0\n",
    "        for i in range(1, len(nums)):\n",
    "            leftSum += nums[i - 1] \n",
    "            rightSum -= nums[i]\n",
    "            if leftSum == rightSum:\n",
    "                return i\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
